|
In graph theory, a branch of mathematics, a chordal completion of a given undirected graph is a chordal graph on the same vertex set that has as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. The minimum chordal completion is a chordal completion with a few edges as possible. A different type of chordal completion, one that minimizes the size of the maximum clique in the resulting chordal graph, can be used to define the treewidth of . Chordal completions can also be used to characterize several other graph classes including AT-free graphs, claw-free AT-free graphs, and cographs. The minimum chordal completion was one of twelve computational problems whose complexity was listed as open in the 1979 book ''Computers and Intractability''. Applications of chordal completion include modeling the problem of minimizing fill-in when performing Gaussian elimination on sparse symmetric matrices, and reconstructing phylogenetic trees. Chordal completions of a graph are sometimes called triangulations,〔 but this term is ambiguous even in the context of graph theory, as it can also refer to maximal planar graphs. ==Related graph families== A graph is an AT-free graph if and only if all of its minimal chordal completions are interval graphs. is a claw-free AT-free graph if and only if all of its minimal chordal completions are proper interval graphs. And is a cograph if and only if all of its minimal chordal completions are trivially perfect graphs.〔.〕 A graph has treewidth at most if and only if has at least one chordal completion whose maximum clique size is at most . It has pathwidth at most if and only if has at least one chordal completion that is an interval graph with maximum clique size at most . It has bandwidth at most if and only if has at least one chordal completion that is a proper interval graph with maximum clique size at most .〔.〕 And it has tree-depth if and only if it has at least one chordal completion that is a trivially perfect graph with maximum clique size at most .〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chordal completion」の詳細全文を読む スポンサード リンク
|